//P1048 [NOIP 2005 普及组] 采药
#include <bits/stdc++.h>
using namespace std;
int w[2];
int b[1005];
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> w[0] >> w[1];
        for(int j = n; j >= w[0]; j--){ 
            b[j] = max(b[j - w[0]] + w[1], b[j]);
        }
    }
    cout << b[n];
    return 0;
}